package com.leetcodehot.problems;

import java.util.Arrays;

public class problems583 {
    /**
     * 还是一样的题目
     * 对于w2的删除 看成w1的新增
     * 对于w2的新增 看成w1的删除
     * 不存在替换 对于w2的替换看成对于w1的删除后新增 所以替换是两步
     * 记忆化搜索
     */
    /*
    public int minDistance(String word1, String word2) {
        char[] charArray1 = word1.toCharArray();
        char[] charArray2 = word2.toCharArray();
        int len1 = charArray1.length;
        int len2 = charArray2.length;
        int[][] memo = new int[len1 + 1][len2 + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(len1 - 1, len2 - 1, charArray1, charArray2, memo);
    }

    private int dfs(int i, int j, char[] charArray1, char[] charArray2, int[][] memo) {
        if (i < 0) {
            return j + 1;
        }
        if (j < 0) {
            return i + 1;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        //相同
        if (charArray1[i] == charArray2[j]) {
            return memo[i][j] = dfs(i - 1, j - 1, charArray1, charArray2, memo);
        }
        //不同
        int ans = Integer.MAX_VALUE;
        //删除
        ans = Math.min(ans, dfs(i - 1, j, charArray1, charArray2, memo));
        //新增
        ans = Math.min(ans, dfs(i, j - 1, charArray1, charArray2, memo));
        //替换(这里比较特殊 替换看成两步)
        ans = Math.min(ans, dfs(i - 1, j - 1, charArray1, charArray2, memo) + 1);
        return memo[i][j] = ans + 1;
    }
    */

    /**
     * 递推
     */
    public int minDistance(String word1, String word2) {
        char[] charArray1 = word1.toCharArray();
        char[] charArray2 = word2.toCharArray();
        int len1 = charArray1.length;
        int len2 = charArray2.length;
        int[][] f = new int[len1 + 1][len2 + 1];
        for (int j = 0; j <= len2; j++) {
            f[0][j] = j;
        }
        for (int i = 0; i < len1; i++) {
            f[i + 1][0] = i + 1;
            for (int j = 0; j < len2; j++) {
                f[i + 1][j + 1] = charArray1[i] == charArray2[j] ? f[i][j] :
                        Math.min(Math.min(f[i][j + 1], f[i + 1][j]), f[i][j] + 1) + 1;
            }
        }
        return f[len1][len2];
    }


}
